Decision Tree (Pohon Keputusan)¶
Pengertian¶
Decision tree adalah salah satu metode klasifikasi yang paling populer, karena mudah untuk diinterpretasi oleh manusia. Decision tree adalah model prediksi menggunakan struktur pohon atau struktur berhirarki.
Konsep dari pohon keputusan adalah mengubah data menjadi decision tree dan aturan-aturan keputusan. Manfaat utama dari penggunaan decision tree adalah kemampuannya untuk mem-break down proses pengambilan keputusan yang kompleks menjadi lebih simple, sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan.
Decision tree membangun model klasifikasi atau regresi dalam bentuk struktur pohon. Ini memecah dataset menjadi himpunan bagian yang lebih kecil dan lebih kecil sementara pada saat yang sama pohon keputusan terkait dikembangkan secara bertahap. Hasil akhirnya adalah pohon dengan simpul keputusan dan simpul daun. Node keputusan (mis., Outlook) memiliki dua atau lebih cabang (mis., Sunny, Overcast, dan Rainy). Node daun (mis., Play) mewakili klasifikasi atau keputusan. Node keputusan teratas dalam pohon yang sesuai dengan prediktor terbaik disebut simpul akar. Pohon keputusan dapat menangani data kategorikal dan numerik.
Entropy¶
Definisi:¶
Entropi adalah ukuran ketidakmurnian, gangguan, atau ketidakpastian dalam banyak contoh.
Apa yang Entropi lakukan?¶
Entropy mengontrol bagaimana Decision Tree memutuskan untuk membagi data. Ini sebenarnya mempengaruhi bagaimana Pohon Keputusan menarik batas-batasnya
Mencari Entropy¶
Untuk menghitung Information gain perlu dihitung dahulu nilai informasi dalam suatu bits dari suatu kumpulan obyek. Cara penghitungan dilakukan dengan menggunakan konsep entropi. Entropi menyatakan impurity suatu kumpulan obyek . Berikut merupakan definisi dari entropi suatu ruang sampel data (S),sebagai berikut
The Equation of Entropy(Rumus Entropy):¶
$$ Entropy(S) = \sum_{i=1}^n {-P_i\log_2{P_i}} $$
Keterangan :
S = ruang sampel data yang di gunakaan untuk data pelatihan
n = jumlah partisi
Pi = Probability dari Pi terhadap P
Information Gain¶
Information gain (IG) mengukur seberapa banyak "informasi" yang diberikan fitur kepada kita tentang kelas.
– Fitur yang mempartisi dengan sempurna harus memberikan informasi yang maksimal.
– Fitur-fitur yang tidak terkait tidak boleh memberikan informasi.
• Ini mengukur pengurangan entropi.
- Entropi: (im) kemurnian dalam koleksi contoh yang sewenang-wenang.
Apakah yang dimaksud dengan Informasi dan mengapa itu penting di Decision Tree?¶
Definisi: Perolehan informasi (IG) mengukur seberapa banyak "informasi" yang diberikan fitur kepada kita tentang kelas. Kenapa itu penting? Perolehan informasi adalah kunci utama yang digunakan oleh Algoritma Decision Tree untuk membangun Decision Tree. Algoritma Decision Trees akan selalu berusaha memaksimalkan perolehan Informasi. Atribut dengan perolehan Informasi tertinggi akan diuji / dipisah terlebih dahulu.
The Equation of Information gain(Rumus Information Gain):¶
$$ Gain(S,A) = entropy(S)-\sum_{i=1}^n \frac{|s_i|}{|s|}\quad x \quad entropy(S_i) $$
Keterangan :
S = ruang sampel data yang di gunakaan untuk data pelatihan
A = sebagai atribut data
n = jumlah partisi
Si = Probability dari Si terhadap S
Data Berikut untuk menghitung Entropy,Gain yang ada di tiap data tersebut menggunakan hitungan manual :¶
| Customer ID | Gender | Car Type | Shirt Size | Class |
|---|---|---|---|---|
| 1 | M | Family | Small | C0 |
| 2 | M | Sports | Medium | C0 |
| 3 | M | Sports | Medium | C0 |
| 4 | M | Sports | Large | C0 |
| 5 | M | Sports | Extra Large | C0 |
| 6 | M | Sports | Extra Large | C0 |
| 7 | F | Sports | Small | C0 |
| 8 | F | Sports | Small | C0 |
| 9 | F | Sports | Medium | C0 |
| 10 | F | Luxury | Large | C0 |
| 11 | M | Family | Large | C1 |
| 12 | M | Family | Extra Large | C1 |
| 13 | M | Family | Medium | C1 |
| 14 | M | Luxury | Extra Large | C1 |
| 15 | F | Luxury | Small | C1 |
| 16 | F | Luxury | Small | C1 |
| 17 | F | Luxury | Medium | C1 |
| 18 | F | Luxury | Medium | C1 |
| 19 | F | Luxury | Medium | C1 |
| 20 | F | Luxury | Large | C1 |
Pertama¶
Kita harus menghitung Entropy terlebih dahulu dengan menggunakan rumus $Entropy(S)$
$P_i = C0 = , P(C0)=P_1 = \frac{10}{20}$
$P_i = C0 = , P(C1)=P_2 = \frac{10}{20}$ $$ Entropy(S) = {-\frac{10}{20}\log_2{\frac{10}{20}}}{-\frac{10}{20}\log_2{\frac{10}{20}}}= 1 $$
Kedua¶
Sudah dicari Entropynya = 1 maka selanjutnya mencari tiap Gainnya
Gain dari Gender dari tiap Value,berikut Rumus untuk menghitung entropy dari tiap value (Male,Female)
Gain dari CarType dari tiap Value,berikut Rumus untuk menghitung entropy dari tiap value (Family,Sports,Luxury)
Gain dari Shirt Size dari tiap Value,berikut Rumus untuk menghitung entropy dari tiap value(Small,Medium,Large,ExtraLarge)
Ketiga¶
Menghitung Gain dan Entropy ,sebagai berikut $$ Entropy(Male) = {-\frac{6}{10}\log_2{\frac{6}{10}}}{-\frac{4}{10}\log_2{\frac{4}{10}}}=0,97051 $$
$$ Entropy(Female) = {-\frac{4}{10}\log_2{\frac{4}{10}}}{-\frac{6}{10}\log_2{\frac{6}{10}}}=0,97051 $$
$$ Gain(S,Gender) = 1-(\frac{10}{20}X({-\frac{6}{10}\log_2{\frac{6}{10}}}{-\frac{4}{10}\log_2{\frac{4}{10}}})+\frac{10}{20}X({-\frac{4}{10}\log_2{\frac{4}{10}}}{-\frac{6}{10}\log_2{\frac{6}{10}}}) = 0,029049 $$
$$ Entropy(Family) = {-\frac{1}{4}\log_2{\frac{1}{4}}}{-\frac{3}{4}\log_2{\frac{3}{4}}}=0,81128 $$
$$ Entropy(Sports) = {-\frac{8}{8}\log_2{\frac{8}{8}}}{-\frac{0}{8}\log_2{\frac{0}{8}}}=0 $$
$$ Entropy(Luxury) = {-\frac{1}{8}\log_2{\frac{1}{8}}}{-\frac{7}{8}\log_2{\frac{7}{8}}}=0,54356 $$
$$ Gain(S,CarType) = 1-(\frac{4}{20}X({-\frac{1}{4}\log_2{\frac{1}{4}}}{-\frac{3}{4}\log_2{\frac{3}{4}}})+\frac{8}{20}X({-\frac{8}{8}\log_2{\frac{8}{8}}}{-\frac{0}{8}\log_2{\frac{0}{8}}}+\frac{8}{20}X({-\frac{1}{8}\log_2{\frac{1}{8}}}{-\frac{7}{8}\log_2{\frac{7}{8}}}) = 0,62032 $$
$$ Entropy(Small) = {-\frac{3}{5}\log_2{\frac{3}{5}}}{-\frac{2}{5}\log_2{\frac{2}{5}}}=0,97095 $$
$$ Entropy(Medium) = {-\frac{3}{7}\log_2{\frac{3}{7}}}{-\frac{4}{7}\log_2{\frac{4}{7}}}=0,98523 $$
$$ Entropy(Large) = {-\frac{2}{4}\log_2{\frac{2}{4}}}{-\frac{2}{4}\log_2{\frac{2}{4}}}=1 $$
$$ Entropy(ExtraLarge) = {-\frac{2}{4}\log_2{\frac{2}{4}}}{-\frac{2}{4}\log_2{\frac{2}{4}}}=1 $$
$$ Gain(S,ShirtSize) = 1-(\frac{5}{20}X({-\frac{3}{5}\log_2{\frac{3}{5}}}{-\frac{2}{5}\log_2{\frac{2}{5}}})+\frac{7}{20}X({-\frac{3}{7}\log_2{\frac{3}{7}}}{-\frac{4}{7}\log_2{\frac{4}{7}}}+\frac{4}{20}X({-\frac{2}{4}\log_2{\frac{2}{4}}}{-\frac{2}{4}\log_2{\frac{2}{4}}}+\frac{4}{20}X({-\frac{2}{4}\log_2{\frac{2}{4}}}{-\frac{2}{4}\log_2{\frac{2}{4}}}) = 0,012433 $$
Dapat Diperoleh bahwa Gain yang paling terbesar adalah $Gain(S,CarType)$,maka dapat disimpulkan bahwa Gain CarType adalah faktor terpenting dalam membuat decision tree
Berikut Hasil dari Decision Tree yang telah dibuat:
https://raw.githubusercontent.com/WahyuZ98/Wahyu_Zainur.github.io/master/node33.jpg
Contoh Data yang telah didapatkan untuk menghitung entropy,gain dengan program,sebagai berikut:¶
Pertama¶
Kita harus mengimport/memasukkan data dengan meng-coding program tersebut dengan menggunakan bahasa pemrograman python (jupyter notebook)
import pandas as pd from sklearn.preprocessing import LabelEncoder from sklearn.tree import DecisionTreeClassifier from sklearn import tree data = pd.read_excel("data_informationgain.xlsx") df = pd.DataFrame(data) df.style.hide_index()
| Customer ID | Gender | Car Type | Shirt Size | Class |
|---|---|---|---|---|
| 1 | M | Family | Small | C0 |
| 2 | M | Sports | Medium | C0 |
| 3 | M | Sports | Medium | C0 |
| 4 | M | Sports | Large | C0 |
| 5 | M | Sports | Extra Large | C0 |
| 6 | M | Sports | Extra Large | C0 |
| 7 | F | Sports | Small | C0 |
| 8 | F | Sports | Small | C0 |
| 9 | F | Sports | Medium | C0 |
| 10 | F | Luxury | Large | C0 |
| 11 | M | Family | Large | C1 |
| 12 | M | Family | Extra Large | C1 |
| 13 | M | Family | Medium | C1 |
| 14 | M | Luxury | Extra Large | C1 |
| 15 | F | Luxury | Small | C1 |
| 16 | F | Luxury | Small | C1 |
| 17 | F | Luxury | Medium | C1 |
| 18 | F | Luxury | Medium | C1 |
| 19 | F | Luxury | Medium | C1 |
| 20 | F | Luxury | Large | C1 |
Kedua¶
Merubah label / kolom yang ada di data diatas untuk bisa dihitung dengan menggunakan code python,yaitu untuk memudahkan pengguna agar bisa menghitung code yang nanti akan digunakan . Pada gender hanya menggunakan biner (0,1){F,M}. Pada cartype menggunakan inisialisasi angka urutan (0,1,2){Familiy,Luxury,Sports} . Pada Shirt Size menggunakan inisialisasi angka urutan (0,1,2,3){Small,Medium,Large,ExtraLarge}.Berikut codenya
lab= LabelEncoder() df["gender_n"] = lab.fit_transform(df["Gender"]) df["car_type_n"] = lab.fit_transform(df["Car Type"]) df["shirt_size_n"] = lab.fit_transform(df["Shirt Size"]) df["class_n"] = lab.fit_transform(df["Class"]) df.style.hide_index()
Berikut Tampilan yang telah di inisialisasi menjadi angka
| Customer ID | Gender | Car Type | Shirt Size | Class | gender_n | car_type_n | shirt_size_n | class_n |
|---|---|---|---|---|---|---|---|---|
| 1 | M | Family | Small | C0 | 1 | 0 | 3 | 0 |
| 2 | M | Sports | Medium | C0 | 1 | 2 | 2 | 0 |
| 3 | M | Sports | Medium | C0 | 1 | 2 | 2 | 0 |
| 4 | M | Sports | Large | C0 | 1 | 2 | 1 | 0 |
| 5 | M | Sports | Extra Large | C0 | 1 | 2 | 0 | 0 |
| 6 | M | Sports | Extra Large | C0 | 1 | 2 | 0 | 0 |
| 7 | F | Sports | Small | C0 | 0 | 2 | 3 | 0 |
| 8 | F | Sports | Small | C0 | 0 | 2 | 3 | 0 |
| 9 | F | Sports | Medium | C0 | 0 | 2 | 2 | 0 |
| 10 | F | Luxury | Large | C0 | 0 | 1 | 1 | 0 |
| 11 | M | Family | Large | C1 | 1 | 0 | 1 | 1 |
| 12 | M | Family | Extra Large | C1 | 1 | 0 | 0 | 1 |
| 13 | M | Family | Medium | C1 | 1 | 0 | 2 | 1 |
| 14 | M | Luxury | Extra Large | C1 | 1 | 1 | 0 | 1 |
| 15 | F | Luxury | Small | C1 | 0 | 1 | 3 | 1 |
| 16 | F | Luxury | Small | C1 | 0 | 1 | 3 | 1 |
| 17 | F | Luxury | Medium | C1 | 0 | 1 | 2 | 1 |
| 18 | F | Luxury | Medium | C1 | 0 | 1 | 2 | 1 |
| 19 | F | Luxury | Medium | C1 | 0 | 1 | 2 | 1 |
| 20 | F | Luxury | Large | C1 | 0 | 1 | 1 | 1 |
Ketiga¶
Setelah merubah label menjadi inisialisasi angka (numerik) melanjutkan ke code berikutnya untuk bisa dihitung dan code berikut untuk penghapusan fitur /label yang tidak diperlukan
inputs = df.drop(["Customer ID","Gender","Car Type","Shirt Size", "Class","class_n"],axis="columns") target = df["class_n"]
Keempat¶
Membuat Klasifikasi fitur untuk bisa dibuat Pohon Keputusan (Decision Tree)untuk bisa di classifier .
model = DecisionTreeClassifier(criterion="entropy",random_state=100) model.fit(inputs,target)
DecisionTreeClassifier(class_weight=None, criterion='entropy', max_depth=None, max_features=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, min_samples_leaf=1, min_samples_split=2, min_weight_fraction_leaf=0.0, presort=False, random_state=100, splitter='best')
from matplotlib import pyplot as plt tree.plot_tree(model.fit(inputs,target), max_depth=None, feature_names=["Customer ID","Gender","Car Type","Shirt Size"],class_names=["C0","C1"], label="all", filled=True, impurity=True, node_ids=True, proportion=True, rotate=True, rounded=True, precision=3, ax=None, fontsize=None)
Text(167.4, 195.696, 'node #0\nGender <= 1.5\nentropy = 1.0\nsamples = 100.0%\nvalue = [0.5, 0.5]\nclass = C0'), Text(125.55000000000001, 152.208, 'node #1\nCar Type <= 0.5\nentropy = 0.65\nsamples = 60.0%\nvalue = [0.167, 0.833]\nclass = C1'), Text(83.7, 108.72, 'node #2\nentropy = 0.0\nsamples = 10.0%\nvalue = [0.0, 1.0]\nclass = C1'), Text(167.4, 108.72, 'node #3\nGender <= 0.5\nentropy = 0.722\nsamples = 50.0%\nvalue = [0.2, 0.8]\nclass = C1'), Text(83.7, 65.232, 'node #4\nCar Type <= 2.5\nentropy = 0.918\nsamples = 15.0%\nvalue = [0.333, 0.667]\nclass = C1'), Text(41.85, 21.744, 'node #5\nentropy = 0.0\nsamples = 10.0%\nvalue = [0.0, 1.0]\nclass = C1'), Text(125.55000000000001, 21.744, 'node #6\nentropy = 0.0\nsamples = 5.0%\nvalue = [1.0, 0.0]\nclass = C0'), Text(251.10000000000002, 65.232, 'node #7\nCar Type <= 1.5\nentropy = 0.592\nsamples = 35.0%\nvalue = [0.143, 0.857]\nclass = C1'), Text(209.25, 21.744, 'node #8\nentropy = 1.0\nsamples = 10.0%\nvalue = [0.5, 0.5]\nclass = C0'), Text(292.95, 21.744, 'node #9\nentropy = 0.0\nsamples = 25.0%\nvalue = [0.0, 1.0]\nclass = C1'), Text(209.25, 152.208, 'node #10\nentropy = 0.0\nsamples = 40.0%\nvalue = [1.0, 0.0]\nclass = C0')]
Berikut Hasil Dari Decision Tree,Program dari Code sebagai berikut :
https://raw.githubusercontent.com/WahyuZ98/Wahyu_Zainur.github.io/master/decisiontree.png